package com.leetcode;

import java.util.List;

/**
 * 合并K个升序链表
 */
public class No23 {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode head = null, tail = null;
        while (true) {
            int index = -1;
            for (int i = 0; i < lists.length; i++) {
                if (lists[i] == null) {
                    continue;
                }
                if (index == -1 || lists[index].val > lists[i].val) {
                    index = i;
                }
            }
            if (index == -1) {
                break;
            }
            if (head == null) {
                head = tail = lists[index];
            } else {
                tail.next = lists[index];
                tail = tail.next;
            }
            lists[index] = lists[index].next;
        }
        return head;
    }
}
